package sort

import "sort"

func bubbleSort(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		var executeSort = false
		for j := 0; j < len(nums)-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
				executeSort = true
			}
		}
		if !executeSort {
			return nums
		}
	}
	return nums
}

func bubbleSort1(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		var sortNum bool
		for j := 0; j < len(nums)-i-1; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
				sortNum = true
			}
		}
		if !sortNum {
			break
		}
	}
	return nums
}

/**
 * @Description 912. Sort an Array
 * @Author kami
 * @Date 2023/8/13 8:41
 **/
func selectSort(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		var minIdx = i
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[minIdx] {
				minIdx = j
			}
		}
		if minIdx != i {
			nums[i], nums[minIdx] = nums[minIdx], nums[i]
		}
	}
	return nums
}

func selectSort1(nums []int) []int {
	for i := 0; i < len(nums)-1; i++ {
		var minIdx = i
		for j := i + 1; j < len(nums); j++ {
			if nums[j] < nums[minIdx] {
				minIdx = j
			}
		}
		if minIdx != i {
			nums[minIdx], nums[i] = nums[i], nums[minIdx]
		}
	}
	return nums
}

/*
*
 */
func insertSort(nums []int) []int {
	for i := 1; i < len(nums); i++ {
		for j := i - 1; j >= 0; j-- {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			} else {
				break
			}
		}
	}
	return nums
}

func insertSort1(nums []int) []int {
	for i := 0; i < len(nums)-1; i++ {
		for j := i + 1; j > 0; j-- {
			if nums[j] < nums[j-1] {
				nums[j], nums[j-1] = nums[j-1], nums[j]
			}
		}
	}
	return nums
}

func quickSort(nums []int) []int {
	quickSortDfs(nums, 0, len(nums)-1)
	return nums
}

func quickSortDfs(nums []int, low, high int) {
	if low < high {
		i := low
		j := high
		x := nums[i]

		for i < j {
			// 从右边开始找第一个"小于fn" x的数
			for i < j && nums[j] > x {
				j--
			}
			if i < j {
				nums[i] = nums[j]
				i++
			}

			// 从左边开始找第一个"大于" x的数
			for i < j && nums[i] < x {
				i++
			}
			if i < j {
				nums[j] = nums[i]
				j--
			}
		}
		nums[i] = x
		quickSortDfs(nums, low, i-1)
		quickSortDfs(nums, i+1, high)
	}
}

func quickSort1(nums []int) []int {
	quickSortDfs1(nums, 0, len(nums)-1)
	return nums
}

func quickSortDfs1(nums []int, low, high int) {
	if low < high {
		var left = low
		var right = high
		var pvox = nums[low]
		for left < right {
			// 从右往左找第一个小于锚点的值
			for nums[right] > pvox && right > left {
				right--
			}
			if right > left {
				nums[left] = nums[right]
				left++
			}

			for nums[left] < pvox && left < right {
				left++
			}
			if left < right {
				nums[right] = nums[left]
				right--
			}
		}
		nums[left] = pvox
		quickSortDfs1(nums, low, left-1)
		quickSortDfs1(nums, left+1, high)
	}
}

func countPairs(nums []int, target int) int {
	sort.Ints(nums)
	var res int
	for i, curVal := range nums {
		for j := i + 1; j < len(nums); j++ {
			if curVal+nums[j] < target {
				res++
			} else {
				break
			}
		}
	}
	return res
}

func MySort(arr []int) []int {
	// write code here
	var res = make([]int, len(arr))

	for i, num := range arr {
		res[i] = num
	}

	quickMySort(res, 0, len(arr)-1)
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}

	return res
}

func quickMySort(arr []int, low, high int) {
	if low < high {
		var left = low
		var right = high
		var val = arr[left]

		for left < right {
			// 从右向左
			for left < right && arr[right] < val {
				right--
			}
			if left < right {
				arr[left] = arr[right]
				left++
			}
			// 从左向右
			for left < right && arr[left] > val {
				left++
			}
			if left < right {
				arr[right] = arr[left]
				right--
			}

		}
		arr[left] = val
		quickMySort(arr, low, left-1)
		quickMySort(arr, left+1, high)
	}
}
